import heapq


class Solution:
    def findTheCity(self, n: int, edges: list, distanceThreshold: int) -> int:
        adj = [[] for _ in range(n)]
        for edge in edges:
            adj[edge[0]].append((edge[1], edge[2]))
            adj[edge[1]].append((edge[0], edge[2]))
        res = 0
        minArrive = 2**31
        for root in range(n):
            queue = []
            visited = set()
            queue.append((0, root))
            while queue:
                dis, ele = heapq.heappop(queue)
                if ele in visited:
                    continue
                visited.add(ele)
                for nextEle, nextDis in adj[ele]:
                    if dis + nextDis <= distanceThreshold:
                        heapq.heappush(queue, (dis + nextDis, nextEle))
            if len(visited) == minArrive:
                res = max(root, res)
            elif len(visited) < minArrive:
                minArrive = len(visited)
                res = root

        return res
